/** \file    group.h
  * \brief   Manages merge of patches (segments) in groups.
  * \date    2002
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/include/xtd/group.h,v 1.1 2004/12/10 05:10:45 cscom1r4 Exp $
  */

#ifndef _group_h_
#define _group_h_

namespace xtd {

// see Forest of nonoverlapping sets in Algorithms book

// C - (not const!) container with data associated with each patch, datum has to have 'parent' member of the type
// T=C::value_type::parent_type that is used in indexing of C, and integer 'rank' member. 
// One special value of T means that a patch having this value is root (delegate) of a set. 
// This special value is returned by static C::no_parent_value()

// typical superclass of objects in C
template <class T=size_t>
struct patch {
	//organization of groups
	typedef T parent_type;
	parent_type parent;				///< index of piece to parent with
	int rank;

	patch()
		{ xtd::make_set(*this); }
	static parent_type no_parent_value()
		{ return parent_type(-1); }
	void subdue(patch &child)
		{}
	bool is_root() const
		{ return parent == no_parent_value(); }
};

///initializes fields of a patch, creating single element set from it
template <class V>
inline void make_set(V &v)
{
	v.parent = V::no_parent_value();
	v.rank = 0;
}

template <class C>
inline typename C::value_type::parent_type find_root_idx(C &c, typename C::value_type::parent_type idx)
{
	C::value_type &v = c[idx];
	if (v.is_root())
		return idx;
	return v.parent = find_root_idx(c, v.parent);
}

template <class C>
inline typename C::value_type &find_root(C &c, typename C::value_type::parent_type idx)
{
	return c[find_root_idx(c, idx)];
}

///\return true if ridx1 becomes common root now
template <class C>
inline bool link_roots(C &c, 
	typename C::value_type::parent_type ridx1, typename C::value_type::parent_type ridx2)
{
	if (c[ridx1].rank > c[ridx2].rank) {
		c[ridx2].parent = ridx1;
		c[ridx1].subdue(c[ridx2]);
		return true;
	} else {
		c[ridx1].parent = ridx2;
		c[ridx2].subdue(c[ridx1]);
		if (c[ridx1].rank == c[ridx2].rank) 
			++c[ridx2].rank;
		return false;
	}
}

///\return new common root
template <class C>
inline typename C::value_type::parent_type link_roots2(C &c, 
	typename C::value_type::parent_type ridx1, typename C::value_type::parent_type ridx2)
{
	if (c[ridx1].rank > c[ridx2].rank) {
		c[ridx2].parent = ridx1;
		c[ridx1].subdue(c[ridx2]);
		return ridx1;
	} else {
		c[ridx1].parent = ridx2;
		c[ridx2].subdue(c[ridx1]);
		if (c[ridx1].rank == c[ridx2].rank) 
			++c[ridx2].rank;
		return ridx2;
	}
}

///\return true if two participating patches are in one set
template <class C>
inline bool in_one_set(C &c, 
	typename C::value_type::parent_type idx1, typename C::value_type::parent_type idx2,
	typename C::value_type::parent_type *ridx1=0, typename C::value_type::parent_type *ridx2=0)
{
	typename C::value_type::parent_type r1 = find_root_idx(c, idx1);
	if (ridx1)
		*ridx1 = r1;
	typename C::value_type::parent_type r2 = find_root_idx(c, idx2);
	if (ridx2)
		*ridx2 = r2;
	return r1 == r2;
}

///\return true if two participating patches was not in one set before function call
template <class C>
inline bool union_sets(C &c, 
	typename C::value_type::parent_type idx1, typename C::value_type::parent_type idx2)
{
	C::value_type::parent_type ridx1, ridx2;
	if (in_one_set(c, idx1, idx2, &ridx1, &ridx2))
		return false;
	link_roots(c, ridx1, ridx2);
	return true;
}

template <class C>
inline size_t root_count(const C &c)
{
	size_t count = 0;
	C::const_iterator i(c.begin());
	for (; i != c.end(); ++i) 
		if (i->is_root())
			++count;
	return count;
}

} //namespace xtd

#endif //_group_h_
